package com.hyper_yang.algorithmRecord.pathfinder;

import java.util.HashMap;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;

// A* 寻路算法 (试理解)
// A* 算法是基于 Dijkstra算法的，但通过引入一个启发式函数 h(n)来指导搜索方向，
//从而提高效率。它的核心思想是：每次从待探索的节点中，选择那个预估总代价最低的节点进行扩展。
public class AStar { // A* 算法实现 显示最短距离
//    你现在位于一个 M×N 的迷宫中。迷宫用一个二维字符数组表示，
//    其中 'S' 表示起点，'E' 表示终点，'#' 表示障碍物，'.' 表示可以通过的空地。
//    你只能向上、下、左、右四个方向移动，每移动一步耗费 1 的体力。
//    请你计算从起点到终点的最少体力消耗。如果无法到达，返回 -1。

//    输入格式：
//    第一行包含两个整数 M 和 N (1≤M,N≤100)，表示迷宫的行数和列数。
//    接下来 M 行，每行包含 N 个字符，表示迷宫的布局。保证迷宫中只有一个 'S' 和一个 'E'。

    // Node类用于封装迷宫中的一个位置以及其在 A* 算法中所需的代价信息
    class Node implements Comparable<Node> {
        int row; // 行坐标
        int col; // 列坐标
        int gCost; // 从起点到当前节点的实际代价
        int hCost; // 从当前节点到终点的估计代价 (启发式)
        int fCost; // 评估函数 f(n)=g(n)+h(n) 【A* 算法的目标是选择 f(n)最小的节点进行扩展】
        Node parent; // 用于路径回溯

        public Node(int row, int col, int gCost, int hCost, Node parent) {
            this.row = row;
            this.col = col;
            this.gCost = gCost;
            this.hCost = hCost;
            this.fCost = gCost + hCost;
            this.parent = parent;
        }

        // 用于 PriorityQueue的比较，根据 fCost排序
        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.fCost, o.fCost);
        }

        // 为了在 hashMap中正确使用 Node作为键，需要重写 equals和 hashCode
        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return row == node.row && col == node.col;
        }
    }

    // 启发式函数:
    // 曼哈顿距离 【适用于只能水平或垂直移动的情况】
    public static int heuristic1(int row1, int col1, int row2, int col2) {
        return Math.abs(row1 - row2) + Math.abs(col1 - col2);
    }

    // 欧几里得距离  【适用于可以在任意方向移动的情况】
    public static int heuristic2(int row1, int col1, int row2, int col2) {
        return (int) Math.sqrt((row1 - row2) * (row1 - row2) + (col1 - col2) * (col1 - col2));
    }

    public int solveMaze(char[][] maze) {
        int M = maze.length;
        int N = maze[0].length;

        Node startNode = null;
        Node endNode = null;

        // 查找起点和终点
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < N; col++) {
                if (maze[row][col] == 'S') {
                    startNode = new Node(row, col, 0, 0, null); // gCost初始为 0，hCost待计算
                } else if (maze[row][col] == 'E') {
                    endNode = new Node(row, col, 0, 0, null); // hCost待计算
                }
            }
        }

        if (startNode == null || endNode == null)
            return -1;

        // 初始化 startNode的 hCost和 fCost
        startNode.hCost = heuristic1(startNode.row, startNode.col, endNode.row, endNode.col);
        startNode.fCost = startNode.gCost + startNode.hCost;

        // 根据 fCost排序
        PriorityQueue<Node> openList = new PriorityQueue<>();
        // 存储从起点到某个结点的最小 gCost
        HashMap<Node, Integer> gCosts = new HashMap<>();
        // 存储路径回溯
        HashMap<Node, Node> cameFrom = new HashMap<>();

        // 添加起点到开放列表
        openList.add(startNode);
        gCosts.put(startNode, 0);

        // 定义移动方向 (上, 下, 左, 右)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!openList.isEmpty()) {
            Node current = openList.poll(); // 取出 fCost最小的节点
            // 如果当前节点是终点，返回其 gCost
            if (current.row == endNode.row && current.col == endNode.col)
                return current.gCost;

            // 遍历邻居
            for (int[] dir : directions) {
                int nr = current.row + dir[0];
                int nc = current.col + dir[1];

                // 检查边界和障碍物
                // 跳过无效的邻居
                if (nr < 0 || nr >= M || nc < 0 || nc >= N || maze[nr][nc] == '#') {
                    continue;
                }
                // 记录 gCost
                int newGCost = current.gCost + 1;
                Node neighbor = new Node(nr, nc, newGCost, 0, current);

                // 如果这条路径到 (nr,nc)比之前找到的更优
                if (!gCosts.containsKey(neighbor) || newGCost < gCosts.get(neighbor)) {
                    gCosts.put(neighbor, newGCost);
                    neighbor.hCost = heuristic1(nr, nc, endNode.row, endNode.col);
                    neighbor.fCost = newGCost + neighbor.hCost;
                    openList.add(neighbor);
                    cameFrom.put(neighbor, current);
                }
            }
        }
        // 如果开放列表为空，但未到达终点，说明无路径
        return -1;
    }

    /*
S	.	.	.	.
#	#	.	#	.
.	#	#	#	.
.	#	#	.	.
.	.	.	E	.
     */
    public static void main(String[] args) {
        AStar aStart = new AStar();
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入迷宫的行数 M 和列数 N (用空格分隔):");
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        scanner.nextLine(); // 消耗掉换行符

        char[][] maze = new char[M][N];
        System.out.println("请输入迷宫的布局 (每行用制表符分隔字符):");
        for (int i = 0; i < M; i++) {
            String line = scanner.nextLine();
            // 使用制表符分割字符串，并取每个分割后的字符串的第一个字符
            String[] chars = line.split("\t");
            for (int j = 0; j < N; j++) {
                if (j < chars.length) { // 防止列数不匹配
                    maze[i][j] = chars[j].charAt(0);
                } else {
                    // 如果某行字符不够，可以根据需要处理，例如填充空格或报错
                    maze[i][j] = ' '; // 示例：填充空格
                }
            }
        }

        int result = aStart.solveMaze(maze);
        System.out.println("最短路径长度: " + result);

        scanner.close();
    }
}
/*
//        Scanner scanner = new Scanner(System.in);
//        int M = scanner.nextInt();
//        int N = scanner.nextInt();
//        scanner.nextLine(); // 消耗掉换行符
//
//        char[][] maze = new char[M][N];
//        for (int i = 0; i < M; i++) {
//            maze[i] = scanner.nextLine().toCharArray();
//        }
//
//        int result = aStart.solveMaze(maze);
//        System.out.println(result);
//
//        scanner.close();
输入
5 5
S....
.#.#.
.###.
.##..
...E.
 */